package com.alg;

import com.algorithm.ListNode;
import com.algorithm.TreeNode;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2019/12/30 11:39
 */
public class TreeTest {
    public static void main(String[] args) {
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        int l = 0, r = nums.length - 1;
        return getMid(nums, l, r);
    }

    private TreeNode getMid(int[] nums, int l, int r) {
        if (l <= r) {
            int mid = (l + r) >> 1;
            TreeNode treeNode = new TreeNode(nums[mid]);
            treeNode.left = getMid(nums, l, mid - 1);
            treeNode.right = getMid(nums, mid + 1, r);
        }
        return null;
    }

    public int hammingWeight(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                res++;
            }
            n = n >> 1;
        }
        return res;
    }

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        int i = 0;
        TreeNode r = root;
        while (r != null || !stack.isEmpty()) {
            while (r != null) {
                stack.push(r.left);
                r = r.left;
            }
            if (!stack.isEmpty()) {
                TreeNode t = stack.pop();
                i++;
                if (i == k) {
                    return t.val;
                }
                r = t.right;
            }
        }
        return 0;
    }

    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            list.add(p.val);
            p = p.next;
        }
        return getTree(list, 0, list.size() - 1);
    }

    private TreeNode getTree(List<Integer> list, int start, int end) {
        if (start <= end) {
            int mid = (start + end) >> 1;
            TreeNode root = new TreeNode(list.get(mid));
            root.left = getTree(list, start, mid - 1);
            root.right = getTree(list, mid + 1, end);
            return root;
        }
        return null;
    }


    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        int val = 0;
        if (t1 != null) val += t1.val;
        if (t2 != null) val += t2.val;
        TreeNode root = new TreeNode(val);
        root.left = mergeTrees(t1 != null ? t1.left : null, t2 != null ? t2.left : null);
        root.right = mergeTrees(t1 != null ? t1.right : null, t2 != null ? t2.right : null);
        return root;
    }

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        midOrder(root);
        return root;
    }

    public void midOrder(TreeNode root) {
        if (root == null) return;
        midOrder(root.right);
        sum += root.val;
        root.val = sum;
        midOrder(root.left);
    }

    public int hammingDistance(int x, int y) {
        int res = 0;
        int temp = x ^ y;
        for (int i = 0; i < 31; i++) {
            if ((temp & 1) == 1) {
                res++;
            }
            temp = temp >> 1;
        }
        return res;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return Collections.emptyList();
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> res = new LinkedList<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            int[] temp = new int[26];
            for (char c : chars) {
                temp[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int t : temp) {
                sb.append(t);
                sb.append("#");
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                ArrayList<String> value = new ArrayList<>();
                value.add(str);
                res.add(value);
                map.put(key, value);
            } else {
                map.get(key).add(str);
            }
        }
        return res;
    }

    public int deepestLeavesSum(TreeNode root) {
        TreeNode p = root;
        Queue<TreeNode> list = new LinkedList<>();
        list.add(p);
        int res = p.val;
        while (!list.isEmpty()) {
            int size = list.size();
            int temp = 0;
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.poll();
                temp += treeNode.val;
                TreeNode l = treeNode.left;
                TreeNode r = treeNode.right;
                if (l != null) list.offer(l);
                if (r != null) list.offer(r);
            }
            res = temp;
        }
        return res;
    }

    public int sumEvenGrandparent(TreeNode root) {
        int res = 0;
        TreeNode p = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                TreeNode l = poll.left;
                TreeNode r = poll.right;
                boolean flg = poll.val % 2 == 0;
                if (l != null) {
                    if (flg) {
                        if (l.left != null)
                            res += l.left.val;
                        if (l.right != null)
                            res += l.right.val;
                    }
                    queue.offer(l);
                }
                if (r != null) {
                    if (flg) {
                        if (r.left != null)
                            res += r.left.val;
                        if (r.right != null)
                            res += r.right.val;
                    }
                    queue.offer(r);
                }
            }
        }
        return res;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return conTree(nums, 0, nums.length - 1);
    }

    private TreeNode conTree(int[] nums, int start, int end) {
        if (start > end) return null;
        int maxIndex = getMaxTree(nums, start, end);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = conTree(nums, start, maxIndex - 1);
        root.right = conTree(nums, maxIndex + 1, end);
        return root;
    }

    private int getMaxTree(int[] nums, int start, int end) {
        int max = start;
        for (int i = start; i <= end; i++) {
            if (nums[i] > max)
                max = i;
        }
        return max;
    }


    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = sortTList(root1);
        List<Integer> list2 = sortTList(root2);
        int list1Len = list1.size();
        int list2Len = list2.size();

        int p1 = 0, p2 = 0;
        List<Integer> res = new ArrayList<>();
        while (p1 < list1Len && p2 < list2Len) {
            Integer p1V = list1.get(p1);
            Integer p2V = list2.get(p2);
            if (p1V < p2V) {
                res.add(p1V);
                p1++;
            } else {
                res.add(p2V);
                p2++;
            }
        }
        while (p1 < list1Len) {
            Integer p1V = list1.get(p1);
            p1++;
            res.add(p1V);
        }
        while (p2 < list2Len) {
            Integer p2V = list2.get(p2);
            p2++;
            res.add(p2V);
        }
        return res;
    }

    private List<Integer> sortTList(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }

    public TreeNode bstToGst2(TreeNode root) {
        if (root == null) return null;
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                list.add(p);
                p = p.right;
            }
        }
        int len = list.size();
        int sum = 0;
        for (int i = len - 1; i >= 0; i++) {
            TreeNode treeNode = list.get(i);
            sum += treeNode.val;
            treeNode.val = sum;
        }
        return root;
    }

    int rootSum = 0;

    public TreeNode bstToGst(TreeNode root) {
        if (root == null) return null;
        bstToGst(root.right);
        sum += root.val;
        root.val = sum;
        bstToGst(root.left);
        return root;
    }

    private int getTotalSum(TreeNode root) {
        if (root == null) return 0;
        return getTotalSum(root.left) + getTotalSum(root.right) + root.val;
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = root;
        while (node != null) {
            if (val > node.val) {
                if (node.right == null) {
                    node.right = new TreeNode(val);
                    return root;
                } else {
                    node = node.right;
                }
            } else {
                if (node.left == null) {
                    node.left = new TreeNode(val);
                    return root;
                } else {
                    node = node.left;
                }
            }
        }
        return new TreeNode(val);
    }


    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> valStack = new Stack<>();
        List<List<Integer>> res = new LinkedList<>();
        int temp = 0;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                valStack.push(p.val);
                temp += p.val;
                p = p.left;
            }
            System.out.println(stack);
            if (!stack.isEmpty()) {
                p = stack.pop();
                temp = temp - p.val;
                p = p.right;
                valStack.pop();
            }
        }
        return res;
    }

    public void construct_paths(TreeNode root, String path, LinkedList<String> paths) {
        if (root != null) {
            path += Integer.toString(root.val);
            if ((root.left == null) && (root.right == null))
                paths.add(path);
            else {
                path += "->";
                construct_paths(root.left, path, paths);
                construct_paths(root.right, path, paths);
            }
        }
    }

    public List<String> binaryTreePaths1(TreeNode root) {
        LinkedList<String> paths = new LinkedList();
        construct_paths(root, "", paths);
        return paths;
    }


    public List<String> binaryTreePaths2(TreeNode root) {
        LinkedList<String> paths = new LinkedList<>();
        if (root == null)
            return paths;
        LinkedList<TreeNode> node_stack = new LinkedList<>();
        LinkedList<String> path_stack = new LinkedList<>();
        node_stack.add(root);
        path_stack.add(Integer.toString(root.val));
        TreeNode node;
        String path;
        while (!node_stack.isEmpty()) {
            node = node_stack.pollLast();
            path = path_stack.pollLast();
            if ((node.left == null) && (node.right == null))
                paths.add(path);
            if (node.left != null) {
                node_stack.add(node.left);
                path_stack.add(path + "->" + Integer.toString(node.left.val));
            }
            if (node.right != null) {
                node_stack.add(node.right);
                path_stack.add(path + "->" + Integer.toString(node.right.val));
            }
        }
        return paths;
    }


    public int sumNumbers(TreeNode root) {
        TreeNode p = root;
        if (p == null) return 0;
        int res = 0;
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> valueStack = new Stack<>();
        nodeStack.push(p);
        valueStack.push(p.val);
        while (!nodeStack.isEmpty()) {
            TreeNode top = nodeStack.pop();
            Integer val = valueStack.pop();
            if (top.left == null && top.right == null) {
                res += val;
            }
            if (top.left != null) {
                nodeStack.push(top.left);
                valueStack.push(val * 10 + top.left.val);
            }
            if (top.right != null) {
                nodeStack.push(top.right);
                valueStack.push(val * 10 + top.right.val);
            }
        }
        return res;
    }
}
